
from Quoridor_game import QuoridorAction, WHITE, BLACK, TIE, QuoridorState, DIRECTIONS, GetNextLocation
import time
from alpha_beta import AlphaBetaSearch
from game_agent import GameAgent
from utils import PriorityQueue
#from NextRow import NextRow

START_DEPTH = 1
INFINITY = 1.0e400

class qouridorError(Exception): pass
    

class anytimeAlphaBeta(AlphaBetaSearch):
    '''
    implementing anytime alpha beta search, raise an exception when time is up
    '''
    def __init__(self, player, max_depth, utility, turnTimeLimit):
        self.turnTimeLimit = turnTimeLimit - 0.01
        self.startTime = time.clock()
        AlphaBetaSearch.__init__(self, player, max_depth, utility)

    def _cutoffTest(self, state, depth):
        #print "any time",(time.clock()-self.startTime)
        if ((time.clock()-self.startTime) > self.turnTimeLimit):
            print "raised exceeding turn time exception "
            raise qouridorError()
        return AlphaBetaSearch._cutoffTest(self, state, depth)
        
    def search(self, current_state):
        return AlphaBetaSearch.search(self, current_state)
        
class IDAnytimeAlphaBeta():
    '''
    implementing the iterative deepenning alpha beta search that uses SelectiveAlphaBetaOrderedSearch
    '''
    def __init__(self, player, max_depth, utility, turnTimeLimit,w = None):
        self.turnTimeLimit = turnTimeLimit
        self.maxDepth = max(max_depth,START_DEPTH)
        self.alfaBeta = SelectiveAlphaBetaOrderedSearch(player, START_DEPTH, utility, turnTimeLimit,w)        
        
    def search(self, current_state):
        self.alfaBeta.max_depth = START_DEPTH
        self.alfaBeta.startTime = time.clock()
        lastBestAction = None
        lastBestValue = None
        lastActionCaseLost = None
        lastValueCaseLost = None
        while self.alfaBeta.max_depth <= self.maxDepth and (self.alfaBeta.max_depth <= current_state.turnsLeft):
            try:
                testTime = time.clock()
                lastBestAction,lastBestValue = self.alfaBeta.search(current_state)
#                print "reached to depth ",self.alfaBeta.max_depth," in ", time.clock()-testTime," sec, best action is ",lastBestAction
                if lastBestValue >= 100000:
                    break
                if lastBestValue <= -100000:
                    lastBestAction = lastActionCaseLost
                if lastValueCaseLost == None or lastBestValue > lastValueCaseLost:
                    lastValueCaseLost = lastBestValue
                    lastActionCaseLost = lastBestAction
            except qouridorError:
#                print 'ecxeption in depth ', self.alfaBeta.max_depth,"exception after ", time.clock()-testTime," sec"
                break
            self.alfaBeta.max_depth += 1
            
#        print 'reached to depth of ', self.alfaBeta.max_depth
        if lastBestValue <= -100000:
            return lastActionCaseLost
        return lastBestAction
    
class SelectiveAlphaBetaSearch(anytimeAlphaBeta):
    '''
    implementing the selctive alpha beta algorithm, using anytime
    '''
    def __init__(self, player, max_depth, utility, turnTimeLimit,w):
        self.w = w 
        if w == None:
            self.w = 1
        anytimeAlphaBeta.__init__(self, player, max_depth, utility, turnTimeLimit)
        
    def search(self, current_state):
        '''
        Search game to determine best action; use alpha-beta pruning.        
        @param current_state: The current game state to start the search from.
        '''
        best_value = -INFINITY
        count = 0
        NumberOfActionInState = len(current_state.getSuccessors().items())
        NumberOfActionsToCheck = NumberOfActionInState * self.w 
        for action, state in current_state.getSuccessors().items():
            if (count > NumberOfActionsToCheck):
                break
            count+=1
            value_fn = self._getValueFn(state)
            value = value_fn(state, best_value, INFINITY, 1)
            if value > best_value:
                best_value = value
                best_action = action
#        print 'search best value ',best_value
        return best_action
    
    def _maxValue(self, state, alpha, beta, depth):
        if self._cutoffTest(state, depth):
            return self.utility(state)
        
        value = -INFINITY
        count = 0
        NumberOfActionInState = len(state.getSuccessors().items())
        NumberOfActionsToCheck = NumberOfActionInState * self.w 
        for successor in state.getSuccessors().values():
            if (count > NumberOfActionsToCheck):
                break
            count+=1
            value_fn = self._getValueFn(successor)
            value = max(value, value_fn(successor, alpha, beta, depth + 1))
            if value >= beta:
                return value
            alpha = max(alpha, value)
#        print 'MAX value ',value
        return value
    
    def _minValue(self, state, alpha, beta, depth):
        if self._cutoffTest(state, depth):
            return self.utility(state)
        count = 0
        NumberOfActionInState = len(state.getSuccessors().items())
        NumberOfActionsToCheck = NumberOfActionInState * self.w 
        value = INFINITY
        for successor in state.getSuccessors().values():
            if (count > NumberOfActionsToCheck):
                break
            count+=1
            value_fn = self._getValueFn(successor)
            value = min(value, value_fn(successor, alpha, beta, depth + 1))
            if value <= alpha:
                return value
            beta = min(beta, value)
#        print 'MIN value ',value
        return value
    
class SelectiveAlphaBetaOrderedSearch(anytimeAlphaBeta):
    '''
    improving SelectiveAlphaBetaSearch by sorting the get successored state according to our heuristic
    '''
    def __init__(self, player, max_depth, utility, turnTimeLimit,w):
        self.w = w 
        if w == None:
            self.w = 1 
        anytimeAlphaBeta.__init__(self, player, max_depth, utility, turnTimeLimit)
        
    def minEvaluator(self, actionState):
            return  self.utility(actionState[1])
        
    def maxEvaluator(self, actionState):
            return  -self.utility(actionState[1])
        
    def makeMinHeap(self, currState):        
        heap = PriorityQueue(self.minEvaluator)
        cachedLocations = currState.checkedLocations
        for action, state in currState.getSuccessors().items():
            state.checkedLocations = cachedLocations
            state.father = currState
            heap.append([action,state])
        return heap
    
    def makeMaxHeap(self, currState):        
        heap = PriorityQueue(self.maxEvaluator)
        cachedLocations = currState.checkedLocations
        for action, state in currState.getSuccessors().items():
            state.checkedLocations = cachedLocations
            state.father = currState
            heap.append([action,state])
        return heap
    
    def search(self, current_state):
        '''
        Search game to determine best action; use alpha-beta pruning.
        
        @param current_state: The current game state to start the search from.
        '''
        best_value = -INFINITY
        count = 0
        current_state.checkedLocations = [{} for i in range(current_state.numPieces)]
        heap = self.makeMaxHeap(current_state)
        
        NumberOfActionInState = len(heap)
        NumberOfActionsToCheck = NumberOfActionInState * self.w 
        
        while heap and len(heap) > 0:
            if (count > NumberOfActionsToCheck):
                break
            count+=1
            actState = heap.pop()
            value_fn = self._getValueFn(actState[1])

            value = value_fn(actState[1], best_value, INFINITY, 1)
            if value > best_value:
                best_value = value
                best_action = actState[0]
        
        return best_action,best_value
    
    def _cutoffTest(self, state, depth):
        return anytimeAlphaBeta._cutoffTest(self, state, depth) or state.getTurnsLeft() <= 0
    
    def _maxValue(self, state, alpha, beta, depth):
        if self._cutoffTest(state, depth):
            return self.utility(state)
        
        heap = self.makeMaxHeap(state)
        value = -INFINITY
        count = 0
        NumberOfActionInState = len(heap)
        NumberOfActionsToCheck = NumberOfActionInState * self.w 
        while heap and len(heap) > 0:
            if (count > NumberOfActionsToCheck):
                break
            count+=1
            actState = heap.pop()
            value_fn = self._getValueFn(actState[1])

            value = max(value, value_fn(actState[1], alpha, beta, depth + 1))
            if value >= beta:
                return value
            alpha = max(alpha, value) 

        return value
    
    def _minValue(self, state, alpha, beta, depth):
        if self._cutoffTest(state, depth):
            return self.utility(state)
        count = 0
        value = INFINITY
        heap = self.makeMinHeap(state)
        NumberOfActionInState = len(heap)
        NumberOfActionsToCheck = NumberOfActionInState * self.w 
        
        while heap and len(heap) > 0:
            if (count > NumberOfActionsToCheck):
                break
            count+=1
            actState = heap.pop()
            value_fn = self._getValueFn(actState[1])
            actState[1].father = state
            value = min(value, value_fn(actState[1], alpha, beta, depth + 1))
            if value <= alpha:
                return value
            beta = min(beta, value) 

        return value
 